package dfsAllPaths;

import java.util.Scanner;

/*
输入：
5 3
.#.
#@.
*..
...
#.#
输出：
1:11->12->02
2:11->12->13->03->02
3:11->12->22->23->13->03->02
4:11->21->22->12->02
5:11->21->22->12->13->03->02
6:11->21->22->23->13->03->02
7:11->21->22->23->13->12->02
*/
public class Main {
	static char[][] mp; //存放地图，注意数据范围
	static String[][] p;
	static int sx,sy; //起点坐标
	static int tx,ty; //终点坐标
	static int Hx,Wy; //地图总计Wy行，Hx列
	static int num; //路径数量计数
	static int m,n; //m行n列
	static int[][] dx = {
			{-1, 0},  //下走，坐标偏移量
			{ 0, 1},  //右走，坐标偏移量
			{ 1, 0},  //上走，坐标偏移量
			{ 0,-1}   //左走，坐标偏移量
	};
	
	//输入参数为当前坐标
	static void dfs(int x,int y) {
		//从当前坐标开始按左上右下四个方向分别dfs
		for(int i=0;i<4;i++) {
			//当前dfs的目标点
			int nx = x + dx[i][0]; //坐标x位置加偏移量
			int ny = y + dx[i][1]; //坐标y位置加偏移量
			//逐一判断限制情况
			//超出地图范围
			if(nx>=Hx||nx<0||ny<0||ny>=Wy)
				continue; //不再进一步dfs
			//碰到终点
			if(mp[ny][nx] == '*') {
				//此时即找到一个可行路径
				num++; //找到的路径数量加一
				//输出到终点的路径
				System.out.printf("%d:%s->%d%d\n", num,p[y][x],nx,ny);
				//继续查找其他可能路径
				continue;
			}
			//碰到可走的路径，继续dfs
			if(mp[ny][nx] == '.') {
				mp[ny][nx] = '#';  //保存现场，设为已用路径
				
				//记录路径
				p[ny][nx] = String.format("%s->%d%d", p[y][x],nx,ny);
				
				//从这位置继续dfs
				dfs(nx,ny);
				
				mp[ny][nx] = '.';  //回复现场，回溯后可再用路径
			}
		}
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		//初始化地图
		String[] nums = sc.nextLine().split(" ");
		Wy = Integer.parseInt(nums[0]); //行数
		Hx = Integer.parseInt(nums[1]); //列数
		
		mp = new char[Wy][];  //初始化地图
		p = new String[Wy][]; //初始化路径数组
		
		for(int y=0;y<Wy;y++){//按行数循环
			//实例化表示行的子数组
			mp[y] = new char[Hx];
			//实例化路径数组
			p[y] = new String[Hx];
			
			String line = sc.nextLine();//读取行
			for(int x=0;x<Hx;x++) {//按列数循环
				mp[y][x] = line.charAt(x);
				//判断是否读到起点或终点
				if(mp[y][x] == '@') {
					sx = x;  //列，x坐标
					sy = y;  //行，y坐标
				}
				
				if(mp[y][x] == '*') {
					tx = x;  //列，x坐标
					ty = y;  //行，y坐标
				}
			}
		}
		//保存起点路径
		p[sy][sx] = String.format("%d%d",sx,sy);
		//开始dfs
		dfs(sx,sy);

	}
	
	
}
